package src.greed;

public class no134 {//加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] remain = new int[gas.length];//记录每一站 加油 - 耗油 后的剩余量
        for (int i = 0; i < gas.length; i++) {
            remain[i] = gas[i] - cost[i];
        }
        int cur =0;//记录当前还剩的油
        int start = 0;//记录新的起点

        int total = 0;//记录总油量，如果总油量<0，没有起点符合
        for(int num : remain){
            total += num;
        }
        if(total < 0){
            return -1;
        }

        for (int i = 0; i < gas.length; i++) {
            cur+=remain[i];
            if(cur<0){
                start=i+1;
                cur=0;  //cur重新变为0，下一轮循环时cur变为i+1处的remain，实现不符合cur就后移一位的效果
            }
        }
        return start;

    }
}
